5 Exchangeability

Problem of the Day: an urn has distinct balls

1, \dots, n

. Suppose sample

k \leq n

numbers without replacement. What is the expected sum of the top

k - 1

numbers?

Let $X_{1}, \dots, X_{k}$ denote the sample. $M = min {X_{1}, \dots, X_{k}}$ , then $E [X_{1} + \dots + X_{k} - M] = \sum_{i = 1}^{k} E [X_{i}] - E [M] .$
It's easy to see that $(X_{1}, \dots, X_{k})$ is exchangeable. So by claim, $X_{1}, \dots, X_{k}$ iid. So $E [X_{i}] = E [X_{1}] = \sum_{a = 1}^{n} a P (X_{1} = a) = \sum_{a = 1}^{n} \frac{a}{n} = \frac{n + 1}{2} .$
Next, $P (M \geq a) = P (X_{1} \geq a, \dots, X_{k} \geq a) = \frac{(\binom{a - 1}{0}) (\binom{n - a + 1}{k})}{(\binom{n}{k})},$ (hypergeometric distribution) so by tail sum formula, $E [M] = \sum_{a = 1}^{n - k + 1} P (M \geq a) = {(\binom{n}{k})}^{- 1} \sum_{a = 1}^{n - k + 1} (\binom{n - a + 1}{k}) .$
We also have a Hockey-Stick Identity $(\binom{n}{k}) + (\binom{n - 1}{k}) + \dots + (\binom{k}{k}) = (\binom{n + 1}{k + 1}),$ so $E [M] = \frac{(\binom{n + 1}{k + 1})}{(\binom{n}{k})} = \frac{n + 1}{k + 1}$ . So $E [X_{1} + \dots + X_{k} - M] = \frac{k (n + 1)}{2} - \frac{n + 1}{k + 1} = (n + 1) (\frac{k}{2} - \frac{1}{k + 1}) .$

The case of hypergeometric distribution shows that permutation-invariance is an important quality.

A permutation is a one-to-one map $π : {1, \dots, n} \to {1, \dots, n}$ .
There are $n!$ distinct permutations of ${1, \dots, n}$ .

Exchangeability

A sequence $(X_{1}, \dots, X_{n})$ of $n$ RVs on the same probability space is said to be exchangeable if $(X_{π (1)}, \dots, X_{π (n)})$ has the same joint distribution as $(X_{1}, \dots, X_{n})$ for all permutations $π$ of ${1, \dots, n}$ .

Claim

If $(X_{1}, \dots, X_{n})$ is exchangeable, then all subsequences $(X_{i_{1}}, \dots, X_{i_{m}})$ of a given length $m \in {1, \dots, n}$ have the same joint distribution.

For example, $n = 3$ , $(X_{1}, X_{2}, X_{3})$ exchangeable, then $\begin{aligned} P (X_{1} = a, X_{2} = b, X_{3} = c) = P (X_{1} = a, X_{3} = b, X_{2} = c) \\ = & P (X_{2} = a, X_{1} = b, X_{3} = c) = P (X_{2} = a, X_{3} = b, X_{1} = c) \\ = & P (X_{3} = a, X_{2} = b, X_{1} = c) = P (X_{3} = a, X_{1} = b, X_{2} = c) . \end{aligned}$
Sum over $c$ , $\begin{aligned} P (X_{1} = a, X_{2} = b) = P (X_{1} = a, X_{3} = b) \\ = & P (X_{2} = a, X_{1} = b) = P (X_{2} = a, X_{3} = b) \\ = & P (X_{3} = a, X_{2} = b) = P (X_{3} = a, X_{1} = b) . \end{aligned}$
Sum over $b$ , $P (X_{1} = a) = P (X_{2} = a) = P (X_{3} = a) .$
An explanation for the statements:
Since ${(X_{i} = c), c \in Range (X_{i})}$ partitions $Ω$ for any $A \in F$ , then ${A \cap (X_{i} = c), c \in Range (X_{i})}$ partitions $A$ .
By sigma-additivity of P, $P (A) = P [⋃_{c} A \cap (X_{i} = c)] = \sum_{c} P [A \cap (X_{i} = c)] .$
This procedure is referred to as marginalizing out $X_{i}$ .